{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 快速排序算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 第一个版本， naive bayes 选取最后一个元素作为 pivot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Naive_partition(L,p,r):\n",
    "    pivot = L[r] # 主元为最后一个\n",
    "    i = p-1\n",
    "    for j in range(p,r):\n",
    "        if L[j] <= pivot: \n",
    "            i += 1\n",
    "            L[i], L[j] = L[j], L[i]\n",
    "    return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Naive_quick_sort(L,p,r):\n",
    "    '''\n",
    "    Input: \n",
    "    - L: A unordered list.\n",
    "    - p: the first index.\n",
    "    - r: the last index.\n",
    "    Output:\n",
    "    - L: A order list.\n",
    "    '''\n",
    "    if p <= r:\n",
    "        q = Naive_partition(L,p,r)\n",
    "        left = Naive_quick_sort(L,p,q-1)\n",
    "        right = Naive_quick_sort(L,q, r-1)\n",
    "        return left + [L[r]] + right\n",
    "    return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 5, 7, 9, 14]\n"
     ]
    }
   ],
   "source": [
    "## running this to check Naive quick sort\n",
    "L = [5,1,7,9,14,2]\n",
    "print(Naive_quick_sort(L,0,len(L)-1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 第二个版本，增加随机化，避免达到最差状态"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "def Random_partition(L,p,r):\n",
    "    index = random.randint(p,r)\n",
    "    L[index], L[r] = L[r], L[index]\n",
    "    pivot = L[r]\n",
    "    i = p - 1\n",
    "    for j in range(p,r):\n",
    "        if L[j] <= pivot:\n",
    "            i += 1\n",
    "            L[i], L[j] = L[j], L[i]\n",
    "    return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Random_quick_sort(L,p,r):\n",
    "    if p <= r:\n",
    "        q = Random_partition(L,p,r)\n",
    "        left = Random_quick_sort(L,p,q-1)\n",
    "        right = Random_quick_sort(L,q,r-1)\n",
    "        return left + [L[r]] + right\n",
    "    return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 5, 7, 9, 14]\n"
     ]
    }
   ],
   "source": [
    "## running this to check Naive quick sort\n",
    "L = [5,1,7,9,14,2]\n",
    "print(Random_quick_sort(L,0,len(L)-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "torch",
   "language": "python",
   "name": "torch"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
